package com.squirrel.michale.sort2;

import java.util.Arrays;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/1/22 7:37 AM
 * @company Michale Squirrel
 * @link
 * @description 归并排序是冯诺依曼在1945年提出的一种有效的排序算法。它的时间复杂度是O(nlogn),空间复杂度O(n)，它是一个稳定的排序。
 */
public class MergeSort {

    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        process(arr, 0, arr.length - 1);


    }

    public static void process(int[] arr, int left, int right) {

        if (left == right) {
            return;
        }

        int middle = left + ((right - left) >> 1);

        process(arr, left, middle);
        process(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }

    private static void merge(int[] arr, int left, int middle, int right) {
        int[] help = new int[right - left + 1];

        int helpIndex = 0;
        int leftIndex = left;
        int rightIndex = middle + 1;

        while (leftIndex <= middle && rightIndex <= right) {
            help[helpIndex++] = arr[leftIndex] <= arr[rightIndex] ? arr[leftIndex++] : arr[rightIndex++];

//            if (arr[leftIndex] <= arr[rightIndex]) {
//                help[helpIndex] = arr[leftIndex];
//                helpIndex++;
//                leftIndex++;
//            } else {
//                help[helpIndex] = arr[rightIndex];
//                helpIndex++;
//                rightIndex++;
//            }
        }

        while (leftIndex <= middle) {
            help[helpIndex] = arr[leftIndex];
            helpIndex++;
            leftIndex++;
        }

        while (rightIndex <= right) {
            help[helpIndex] = arr[rightIndex];
            helpIndex++;
            rightIndex++;
        }


        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }





    }


    public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        // 步长
        int mergeSize = 1;
        while (mergeSize < N) { // log N
            // 当前左组的，第一个位置
            int L = 0;
            while (L < N) {
                if (mergeSize >= N - L) {
                    break;
                }
                int M = L + mergeSize - 1;
                int R = M + Math.min(mergeSize, N - M - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }
            // 防止溢出
            if (mergeSize > N / 2) {
                break;
            }
            mergeSize <<= 1;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{5, 2, 9, 4, 2, 1, 3, 8};
//        mergeSort1(array);
//        System.out.println(Arrays.toString(array));

        mergeSort2(array);
        System.out.println(Arrays.toString(array));




    }


}
